#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cstring>
#include <cassert>

#ifdef _OPENMP
  #include <omp.h>
#endif

#include <immintrin.h>

#define __AVX2__ 1
#define __AVX512BW__ 1
#define __AVX512CD__ 1
#define __AVX512DQ__ 1
#define __AVX512F__ 1
#define __AVX512VL__ 1
#define __AVX__ 1
#define __SSE2_MATH__ 1
#define __SSE2__ 1
#define __SSE3__ 1
#define __SSE4_1__ 1
#define __SSE4_2__ 1
#define __SSE_MATH__ 1
#define __SSE__ 1
#define __SSSE3__ 1

// Usage: g++ -mavx2 -mavx512f -mavx512dq

#define WIDE (sizeof (__m256i) / sizeof (int))

// #pragma GCC optimize("-O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

using namespace std;

#define PRODUCTION_MAX 512
#define ITEM_MAX 128
#define VN_MAX 128
#define VT_MAX 128
#define STRING_MAX 1024

#ifndef BEHCH_MARK_THREADS
  #define BEHCH_MARK_THREADS 16
#endif

/**
 * index the sorted productions and items
 * @ptr:    means the subscript of production[] or item[]
 * @length: means the same type size
**/
struct Index
{
  int ptr;
  int size;
  Index (): ptr(-1), size(0) { }
};

/**
 * record production like <0>::=<1><2>
 * @A:  <0>
 * @B:  <1>
 * @C:  <2>
**/
struct Production
{
  int A;
  int B;
  int C;
};

/**
 * record production like <0>::=<1>
 * @A:  <0>
 * @B:  <1>
**/
struct Item
{
  int A;
  char B;
};

// index of Item by item.B
Index i_idx[VT_MAX];

Production production[PRODUCTION_MAX];

Item item[ITEM_MAX];

/**
 * dp[i][j][v] = n
 * There are n time of situation for string[i, j] to reduce to v
**/
unsigned int dp[VN_MAX][STRING_MAX][STRING_MAX];

int vn_num;
int production_num;
int item_num;
int string_length;
char str[STRING_MAX];

void print(const unsigned int &x)
{
  printf ("%u ", x);
}

int main(int argc, char **argv)
{
  omp_set_num_threads (BEHCH_MARK_THREADS);
  // basic io
  if (argc != 2)
  { printf ("cyk <input.txt>"); return 0; }

  freopen(argv[1], "r", stdin);
  scanf("%d\n", &vn_num); scanf("%d\n", &production_num);
  for (int i = 0; i < production_num; i++)
    scanf("<%d>::=<%d><%d>\n", &production[i].A, &production[i].B, &production[i].C);
  scanf("%d\n", &item_num);
  for (int i = 0; i < item_num; i++)
    scanf("<%d>::=%c\n", &item[i].A, &item[i].B);
  scanf("%d\n", &string_length); scanf("%s\n", str);

  // sort ascending order by item.B and item.A
  sort (item, item + item_num, [](const Item& a,
                                  const Item& b)
  { return a.B == b.B ? a.A < b.A : a.B < b.B; });

  // init the index which indexed by [item.B]
  for (int i = 0; i < item_num; i++)
  {
    int t = item[i].B;
    if (i_idx[t].ptr == -1) i_idx[t].ptr = i;
    i_idx[t].size++;
  }

  // compute len is 1 situation
  for (int i = 0; i < string_length; i++)
  {
    int t = str[i];
    for (int j = i_idx[t].ptr; j < i_idx[t].ptr + i_idx[t].size; j++)
      dp[item[j].A][0][i] = 1;
  }

  // compute len in [2, string_length] situation
  __m256i mask = _mm256_set_epi32 (0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff);
  __m256i a, b, c;
  for (int i = 1; i < string_length; i++)
  {
    #pragma omp parallel for
    for (int j = 0; j < (string_length - i + ((int)WIDE - 1)) / (int)WIDE; j++)
    {
      int idx = j * WIDE;
      printf ("%d-> %d: (%d, %d)\n", i, omp_get_thread_num (), idx, idx + (int)WIDE);
      for (int k = 0; k < i; k++)
      {
        for (int p = 0; p < production_num; p++)
        {
          a = _mm256_maskload_epi32 ((const int *)&dp[production[p].A][i][idx], mask);
          b = _mm256_maskload_epi32 ((const int *)&dp[production[p].B][k][idx], mask);
          c = _mm256_maskload_epi32 ((const int *)&dp[production[p].C][i - k - 1][idx + k + 1], mask);

          a = _mm256_add_epi32 (a, _mm256_mullo_epi32 (b, c));
          _mm256_maskstore_epi32 ((int *)&dp[production[p].A][i][idx], mask, a);
        }
      }
    }
    #pragma omp barrier
    printf("=================\n");
  }

  printf("%u\n", dp[0][string_length - 1][0]);
  return 0;
}
